//第一行 怪个数，初始化能力值
//第二行怪物的能力值
//防御<=能量直接加
//防御>能量 加最大公约数
//
//#include<iostream>
//#include<vector>
//using namespace std;
//
//int BigNumber(int power,int nu)
//{
//    int ret=0;
//    for(int i =1;i<=power;i++)
//    {
//        if(power%i==0 && nu%i==0)
//        {
//            ret=i;
//        }
//    }
//    return ret;
//
//}
//
//int main()
//{
//    int monster,power;
//
//    while(cin>>monster>>power)
//    {
//        vector<int>mos_po;
//        mos_po.resize(monster);
//
//        for(auto &nu:mos_po)
//        {
//            cin>>nu;
//        }
//
//        //打怪
//        for(auto &nu:mos_po)
//        {
//            if(power>=nu)
//            {
//                power+=nu;
//            }
//            else//最大公约数
//            {
//                power+=BigNumber(power, nu);
//            }
//        }
//        cout<<power<<endl;
//    }
//
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//
////一般情况采用删除
////俩字符串在一起走，中不一样，改或者删，最后开头不一样删
//int Compare(string & mini,string & large)
//{
//    int index1=0,index2=0;
//    int count=0;
//    while(index1<mini.size())
//    {
//        if(mini[index1]!=large[index2])
//        {
//            count++;
//
//            if(mini[index1]==large[index2+1])//插入
//            {
//                index1++;
//                index2+=2;
//            }
//            else if(mini[index1+1]==large[index2])//删除
//            {
//                index1+=2;
//                index2++;
//            }
//            else//修改
//            {
//                index1++;
//                index2++;
//            }
//        }
//        else//相等
//        {
//            index1++;
//            index2++;
//        }
//    }
//
//    //判断index2 当前位置与字符位置相差多少个字符
//    count+=large.size()-index2;
//
//    return count;
//}
//int main()
//{
//    string str1,str2;
//    cin>>str1>>str2;
//
//    if(str1.size()<str2.size())
//    {
//        cout<<Compare(str1,str2)<<endl;
//    }
//    else
//    {
//        cout<<Compare(str2,str1)<<endl;
//    }
//    return 0;
//}


#include<iostream>
#include<vector>
//#include<string>
using namespace std;
//
//void Road(vector<vector<int>> &save ,int row,int line,vector<string>selected,vector<string>&result,vector<string>&result2)
//{
//    if(save.size()==row ||save[row].size()==line||save[row][line]==1)
//    {
//        result=selected;
//
//        if(row==save.size()-1 && line==save[row].size())
//        {
//            result2=result;
//        }
//
//        return;
//    }
//    //入数据
//    string tmp("(");
//    tmp+=row+48;
//    tmp+=",";
//    tmp+=line+48;
//    tmp+=")";
//    selected.push_back(tmp);
//
//    Road(save,row,(line+1),selected,result,result2);//左边
//    Road(save,(row+1),line,selected,result,result2);//下边
//}
//int main()
//{
//    int row,line;
//    cin>>row>>line;
//    vector<vector<int>>save;
//    for(int i=0;i<row;i++)
//    {
//        vector<int>tmp;
//        tmp.resize(line);
//        for(auto &ch :tmp)
//        {
//            cin>>ch;
//        }
//        save.push_back(tmp);
//    }
//
//    vector<string> selected;
//    vector<string> result;
//    vector<string> result2;
//    Road(save,0,0,selected,result,result2);
//    for(auto &ch : result2)
//    {
//        cout<<ch<<endl;
//    }
//
//    return 0;
//}


class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        //最多可以拿11件商品
        //多条路径中寻找最优

        //初始化状态：row=1,line=1
        //状态转移公式：board[i][j]+=board[i][j-1]>board[i-1][j]?board[i][j-1]:board[i-1][j]
        //结果：board[5][5];
        for(int i =0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                //i-1或j-1会不存在
                if(i-1<0&&j-1>=0)
                {
                    board[i][j]+=board[i][j-1];
                }
                else if(i-1>=0 && j-1<0)
                {
                    board[i][j]+=board[i-1][j];
                }
                else//i-1,j-1都存在的情况
                {
                    if(j-1>=0)
                    board[i][j]+=board[i][j-1]>board[i-1][j]?board[i][j-1]:board[i-1][j];
                }
            }
        }
        return  board[board.size()-1][board[0].size()-1];
    }
};

int main()
{
    vector<vector<int>>save;
    vector<int>tmp1{16, 71, 60 };
    vector<int>tmp2{73 ,52, 40 };
    vector<int>tmp3{27 ,24 ,35 };

    save.push_back(tmp1);
    save.push_back(tmp2);
    save.push_back(tmp3);
    Bonus d1;
   cout<< d1.getMost(save)<<endl;
}